package com.leetcode.linkedlist;

import com.leetcode.datastructure.ListNode;

/**
 * @author: ZhouBert
 * @date: 2019/10/2
 * @description: 92. 反转链表 II
 * B
 * 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
 * <p>
 * 说明:
 * 1 ≤ m ≤ n ≤ 链表长度。
 * 示例:
 * 输入: 1->2->3->4->5->NULL, m = 2, n = 4
 * 输出: 1->4->3->2->5->NULL
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ReverseBetween92 {

	public static ListNode reverseBetween(ListNode head, int m, int n) {
		return null;
	}

	/**
	 * 反转链表I
	 * 反转一个单链表。
	 * <p>
	 * 示例:
	 * 输入: 1->2->3->4->5->NULL
	 * 输出: 5->4->3->2->1->NULL
	 * 进阶:
	 * 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
	 * <p>
	 * 206. 反转链表
	 *
	 * @param head
	 * @return
	 */
	public static ListNode reverseList(ListNode head) {
		if (head==null||head.next == null) {
			return head;
		}

		///1.开启一个虚拟节点
//		ListNode dummy = new ListNode(0);
//		dummy.next=head;

		ListNode cur = head;
		ListNode pre = null;
		///todo:核心：将 当前节点(cur) 指向前节点(pre)；然后将当前节点和前节点移位
		while (cur!= null) {
			///临时节点，暂存当前节点的下一节点，用于后移
			ListNode tempNode = cur.next;
			cur.next = pre;

			pre = cur;
			cur = tempNode;
		}
		return pre;
	}

	/**
	 * 仍然有问题！
	 * @param head
	 * @return
	 */
	public static ListNode reverseListWithDummy(ListNode head){
		if (head==null||head.next == null) {
			return head;
		}

		///1.开启一个虚拟节点
		ListNode dummy = new ListNode(0);
		//dummy.next=head;

		ListNode cur=head.next;
		ListNode next=null;
		while (cur!=null){
			next=cur.next;
			cur.next=dummy.next;
			dummy.next=cur;
			cur=next;
		}
		head.next=dummy.next;
		return head;
	}

	/**
	 * 反转单链表（递归）
	 *
	 * @return
	 */
	public static ListNode reverseByRecursive(ListNode head){
		if (head==null||head.next == null) {
			return head;
		}

		ListNode reverseNode = reverseByRecursive(head.next);
		head.next.next=head;
		head.next=null;
		return reverseNode;
	}

	public static void main(String[] args) {
		ListNode node5 = new ListNode(5);
		ListNode node4 = new ListNode(4);
		node4.next = node5;
		ListNode node3 = new ListNode(3);
		node3.next = node4;
		ListNode node2 = new ListNode(2);
		node2.next = node3;
		ListNode node1 = new ListNode(1);
		node1.next = node2;

		///反转链表I

		///ListNode reverseList = reverseList(node1);
		//ListNode reverseList2 = reverseByRecursive(node1);
		ListNode reverseList3 = reverseListWithDummy(node1);
		ListNode listNode = reverseBetween(node1, 1, 2);
		ListNode.print(reverseList3);
	}
}
